/*
剑指 Offer 42. 连续子数组的最大和
解题思路：一次遍历，temp表示保存当前最大，每遍历到一个数，就计算出temp+num和num哪个最大，再与max进行比较。
 */
public class Offer42 {

  public static void main(String[] args) {
    int[] num = new int[]{-2,1,-3,4,-1,2,1,-5,4};
    System.out.println(new Offer42().maxSubArray(num));
  }

  public int maxSubArray(int[] nums) {
   int max = nums[0];
   int temp = 0;
    for (int num : nums) {
      temp = Math.max(num + temp, num);
      max = Math.max(max,temp);
    }
    return max;
  }
}
